Link to this headingShamir’s Secret Sharing Scheme (SSSS)

Web Crypto Version of S4

If the share is a k-degree polynomial then it needs k+1 points to generate the original polynomial with the secret.
If you needs 5 partial keys then you just have to generate 5 points that are on the polynomial.

Link to this headingMath

You use Lagrange polynomials To create polynomials that are Zero at each other point other than 1 specific point.
Using this you can multiply the polynomials together to create a function that goes through each of the points that were provided.

Link to this headingUsage

from binascii import hexlify from Crypto.Cipher import AES from Crypto.Random import get_random_bytes from Crypto.Protocol.SecretSharing import Shamir #Generate Key key = get_random_bytes(16) print(key.hex()) #Generate Shares shares = Shamir.split(2, 5, key, ssss=True) #Print Shares for idx, share in shares: print("Index #{}: {}".format(idx, hexlify(share))) #Use Two shares to get secret key = Shamir.combine(shares[:2], ssss=True) print(key.hex()) # 2d8a50d47df6fee7e8e8b7e2baf6e00b # Index #1: b'77de49da4c10496546fed2fa8a013dcd' # Index #2: b'992262c81e3b91e2b4c47dd2db195b81' # Index #3: b'c3767bc62fdd26601ad218caebee8647' # Index #4: b'44da34ecba6c20ed50b1238279299780' # Index #5: b'1e8e2de28b8a976ffea7469a49de4a46' # 2d8a50d47df6fee7e8e8b7e2baf6e00b

Link to this headingImplementation

import secrets def evaluate_polynomial(coefficients, x): result = 0 for i, coeff in enumerate(coefficients): result += coeff * (x ** i) return result # Reconstruct the secret from shares def reconstruct_secret(shares, max_value): result = 0 n = len(shares) for i in range(n): xi, yi = shares[i] # Calculate Lagrange basis polynomial L_i(0) - we evaluate at x=0 to get the secret numerator = 1 denominator = 1 for j in range(n): if i != j: xj, _ = shares[j] numerator = (numerator * (0 - xj)) % max_value denominator = (denominator * (xi - xj)) % max_value # Calculate L_i(0) = numerator / denominator basis = (numerator * pow(denominator, -1, max_value)) % max_value result = (result + yi * basis) % max_value return result if __name__ == "__main__": shares = 6 min_shares = 3 max_value = 2 ** 31 - 1 secret = secrets.randbelow(max_value) print(f"Secret: {secret}") #Get Random Numbers coefficients = [secret] for r in range(min_shares -1): coefficients.append(secrets.randbelow(max_value)) output = [f"{coeff}*x^{i}" for i, coeff in enumerate(coefficients)] print(f"Polynomial: y = {' + '.join(output)}") #Generate Shares shares_list = [] for i in range(1, shares + 1): x = i y = evaluate_polynomial(coefficients, x) shares_list.append((x, y)) # Print shares for idx, share in shares_list: print(f"Point: ({idx}, {share})") # Reconstruct the secret from shares reconstructed_secret = reconstruct_secret(shares_list[:min_shares], max_value) print(f"Reconstructed Secret: {reconstructed_secret}") # Secret: 90105115 # Polynomial: y = 90105115*x^0 + 116990366*x^1 + 219152435*x^2 # Point: (1, 426247916) # Point: (2, 1200695587) # Point: (3, 2413448128) # Point: (4, 4064505539) # Point: (5, 6153867820) # Point: (6, 8681534971) # Reconstructed Secret: 90105115

Link to this headingImplementation with AES

from binascii import hexlify from Crypto.Cipher import AES from Crypto.Random import get_random_bytes from Crypto.Protocol.SecretSharing import Shamir secret = "This is a secret message." # Convert secret to bytes secret_bytes = secret.encode('utf-8') #Generate Key aes_key_input = get_random_bytes(16) print(aes_key_input.hex()) #Generate Shares shares = Shamir.split(2, 5, aes_key_input) #Print Shares for idx, share in shares: print("Index #{}: {}".format(idx, hexlify(share))) # Encrypt the secret using AES cipher = AES.new(aes_key_input, AES.MODE_GCM) ciphertext, tag = cipher.encrypt_and_digest(secret_bytes) print(f"IV: {cipher.nonce.hex()}, Ciphertext: {ciphertext.hex()}, Tag: {tag.hex()}") #Print Shares for idx, share in shares: print(f"Share Index #{idx}: {hexlify(share)}, Nonce: {cipher.nonce.hex()}, Encrypted_data: {ciphertext.hex()}, Tag: {tag.hex()}") # Reconstruct the key from shares reconstructed_key = Shamir.combine(shares[:2]) print("Reconstructed Key:", reconstructed_key.hex()) # Decrypt the secret using the reconstructed key cipher_reconstructed = AES.new(reconstructed_key, AES.MODE_GCM, nonce=cipher.nonce) decrypted_secret = cipher_reconstructed.decrypt_and_verify(ciphertext, tag) print("Decrypted Secret:", decrypted_secret.decode('utf-8')) # 96f87ae4861e1763acebdd4213cd4139 # Index #1: b'1d2481743b3a39d1e6322b11f115ec1e' # Index #2: b'81418dc5fc564a07395831e5d67c1bf0' # Index #3: b'0a9d7655417264b57381c7b634a4b6d7' # Index #4: b'b98b94a6728eadaa878c040d98aff4ab' # Index #5: b'32576f36cfaa8318cd55f25e7a77598c' # IV: 62eea5e3ac9633d2d2802a502247cf1f, Ciphertext: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Share Index #1: b'1d2481743b3a39d1e6322b11f115ec1e', Nonce: 62eea5e3ac9633d2d2802a502247cf1f, Encrypted_data: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Share Index #2: b'81418dc5fc564a07395831e5d67c1bf0', Nonce: 62eea5e3ac9633d2d2802a502247cf1f, Encrypted_data: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Share Index #3: b'0a9d7655417264b57381c7b634a4b6d7', Nonce: 62eea5e3ac9633d2d2802a502247cf1f, Encrypted_data: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Share Index #4: b'b98b94a6728eadaa878c040d98aff4ab', Nonce: 62eea5e3ac9633d2d2802a502247cf1f, Encrypted_data: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Share Index #5: b'32576f36cfaa8318cd55f25e7a77598c', Nonce: 62eea5e3ac9633d2d2802a502247cf1f, Encrypted_data: eacd662ee1e732e2040131d3f8fd68a2b81166138855aa03c6, Tag: 4f0461bb8efad4e8547e64c1bfb8c9e1 # Reconstructed Key: 96f87ae4861e1763acebdd4213cd4139 # Decrypted Secret: This is a secret message.

Link to this headingSecurity

Ensure that x != 0 because then a term will be removed making it easier to reconstruct the secret.
Ensure that there is not a repeat point.